#include <stdio.h>
#include <stdlib.h>
#include "grafo.h"


struct vertice{
  int custo;
  int custo_artificial;
};

vertice **grafo;
int *arvore;
int *aux;
int CNT = 1;

void init_grafo(int numero_de_nos){
    int i, j;


    arvore = malloc(2*numero_de_nos*(sizeof(int)));
    aux =  malloc(2*numero_de_nos*(sizeof(int)));
    grafo = (vertice **) malloc((numero_de_nos+2)*(sizeof(vertice*)));
    for(i = 0; i <= numero_de_nos+1; i++){
        grafo[i] = malloc((numero_de_nos+2)*(sizeof(vertice)));
    }

    for(i = 0; i < numero_de_nos+2; i++){
        for(j = 0; j < numero_de_nos+2; j++){
            grafo[i][j].custo = 0;
            grafo[i][j].custo_artificial = 1;
        }
    }
}

void add_custo(int custo, int v_o, int v_d){
    grafo[v_o][v_d].custo = custo;
    grafo[v_o][v_d].custo_artificial = 0;
}

int search_node(int v, int *t, int tam){
    int i;

    for(i = 0; i < tam; i++){
        if(t[i] == v) return 1;
    }
    return 0;
}

int find_path (int v_o, int v_d, int numero_de_nos){
    int j;
    static int c = 0, k = 0;
    if(v_o == v_d){
        arvore[0] = v_o;
        return 1;
    }
    /* Inserir o elemento de origem no vetor auxiliar */
    if(k == 0 && c == 0) aux[k++] = v_o;

    for(j = 0; j <= numero_de_nos; j++){
        /**/
        if(j == v_o) continue;

        if(grafo[v_o][j].custo_artificial == 0 && !search_node(j, aux, k)){
            aux[k++] = j;
            c = find_path(j, v_d, numero_de_nos);
            if(c == 1) break;
        }
    }
    if(c == 1) arvore[CNT++] = v_o;
    return c;
}

int *get_arvore(){
    return arvore;
}

vertice** get_grafo(){
    return grafo;
}

int get_count(){
    return CNT;
}

void print_cost(int produto){
    int c = 0, i = CNT-1;

    while (i >= 1){
        c += grafo[arvore[i]][arvore[i-1]].custo;
        i--;
    }

    printf("\n\tCUSTO TOTAL: %d\n", c*produto);
}


void print_arvore()
{
    int i;
    printf("\n\tPATH: ");
    for(i = CNT-1; i >= 0; i--){
        printf("%d ", arvore[i]);
    }
    printf("\n");
}



void print_grafo(int numero_de_nos){
    int i, j;
    for(i = 0; i < numero_de_nos; i++){
        for(j = 0; j < numero_de_nos; j++){
           /* printf("de %d a %d com o custo de %d\n", i, j, grafo[i][j].custo);*/
           printf("\t%d", grafo[i][j].custo);
        }
        printf("\n");
    }
}

